package com.itzmn.newcode.offer;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/15 15:14
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description: 剑指Offer 判断一个数组是否是某二叉树的后序遍历
 *
 *   思路：
 *                    15
 *              10           20
 *         8         14    17    25
 *      5          11        18
 *      后序： 5 8 11 14 10 18 17 25 20 15
 *
 *      找规律：
 *       后序遍历的数组，最后一个是数根，那么前面序列可分为两瓣，小于的是左树，大于的是右树
 *       每个数还可以根据这个方法拆分
 *       12345
 *
 *
 */
public class IsBinSerachTreeLRD {

    public static void main(String[] args) {

        int[] ints = {1,2,3,4,5};
        System.out.println(new IsBinSerachTreeLRD().VerifySquenceOfBST(ints));
    }

    public boolean VerifySquenceOfBST(int [] sequence) {

        if (sequence.length == 0){
            return false;
        }
        boolean check = check(sequence, 0, sequence.length);


        return check;
    }


    public boolean check(int[] arrs,int start,int end){


        if (start == end){
            return true;
        }
        int root = arrs[end - 1];
        int ban = 0;
        for (int i=start;i<end;i++){
            if (arrs[i]>=root){
                ban=i;
                break;
            }
        }

        for (int i=start;i<ban;i++){
            if (arrs[i]>=root){
               return false;
            }
        }
        for (int i=ban;i<end;i++){
            if (arrs[i]<root){
                return false;
            }
        }

        return check(arrs,start,ban)&&check(arrs,ban,end-1);
    }


}
